﻿/*
题目：会议室 II

给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 所需会议室的最小数量 。

https://leetcode.cn/problems/meeting-rooms-ii/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <array>
#include "TreeNode.hpp"
#include "ListNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <algorithm>
#include <functional>
#include <random>

using namespace std;

class Solution {
public:
    // 最大并发数量
    int minMeetingRooms(vector<vector<int>>& intervals) {
        // 按照开始时间排序
        sort(intervals.begin(), intervals.end());
        // 最早结束的在栈顶
        priority_queue<int, vector<int>, greater<int>> heap;

        for (int i = 0; i < intervals.size(); i++) {
            int beg = intervals[i][0], end = intervals[i][1];
            // 如果 当前会议的开始时间 比 最早结束的会议 晚，说明两者不冲突
            // 并且这里使用 if 即可，因为只需要腾出一个房间就好，否则需要维护一个最大值
            if (!heap.empty() && beg >= heap.top()) {
                heap.pop();
            }
            // 否则说明会议冲突
            heap.push(end);
        }

        return heap.size();
    }
};